The present invention relates to positioning technology, in particular, hybrid positioning with blending multiple location technologies.
Location based services are an emerging area of mobile applications that leverages the ability of new devices to calculate their current geographic position and report that to a user or to a service. Some examples of these services include identifying a location of a person or an object in the context of entertainment, work, health or personal life.
Location based services require instantaneous reliable positioning system that can work everywhere. Since no single positioning technology can meet such requirement, combining different positioning technologies to compensate for individual technology's own limitation can provide better results. Such combinations typically include Global Navigation Satellite System (GNSS) along with other non-GNSS positioning systems, such as Wi-Fi and/or cellular positioning technologies. A Hybrid Positioning Engine (HPE) utilizes multiple positioning technologies actively collaborating in order to provide highly accurate location estimation. The limitations of conventional hybrid positioning systems are discussed and a new algorithm for hybrid positioning with Wi-Fi and GPS blending is presented. Wi-Fi discussed herein includes any wireless local area network product that is based on the IEEE 802.11 standards. It should be noted that Wi-Fi is used herein as a non-limiting example of a wireless local area network product. GPS discussed herein includes any satellite positioning system operable to provide location and time information.
Global Positioning System (GPS) is a GNSS that provides autonomous geo-spatial positioning with global coverage using satellites. GNSS allows small electronic receivers to determine their location to within a few meters using time signals transmitted along a Line-Of-Sight (LOS) by radio from satellites. GPS provides highly accurate location results in “open sky” environments, like rural areas and on highways. GPS performs poorly in urban areas where buildings block the view of satellites, and it doesn't provide any coverage inside of buildings.
In indoor environments or in the dense urban canyons, where the low level satellite based signals are critically compromised by obscuration and environmental degradation, Wi-Fi based positioning systems provide better results. Wi-Fi positioning is rapidly gaining acceptance as a complement and supplement to GNSS positioning for outdoor and indoor environments. Wi-Fi hotspots are prevalent in the very areas where GNSS starts to struggle and many smart devices are already equipped with Wi-Fi technology that can support positioning applications.
Performance of GNSS receivers is often poor in deep urban canyons for a number of factors such as low number of visible satellites and heavy multipath caused by multiple high-rises. Wi-Fi positioning works well where GPS performs poorly by utilizing large installed user base of Wi-Fi Access Points (AP). Additionally, low range of Wi-Fi enables reasonable positioning accuracy. An AP or a hotspot has a range of about 20 meters indoors and a greater range outdoors. Hotspot coverage can comprise an area as small as a single room with walls that block radio signals or as large as many square miles, covered by multiple overlapping APs.
The end user needs to know their location awareness anywhere and everywhere, however, no one location technology provides adequate performance in all locations. Blending different technologies for positioning, for example, Wi-Fi and GPS, provides a solution for overall good positioning accuracy. However, for efficient blending certain key points need to be considered. Since GPS performance can degrade quite sharply in deep urban canyons, it's desirable to recognize this early and prevent large GPS drifts. If blending only kicks in when GPS has drifted too much, it will not help correct the UPS back to the right path. Also, blending should be performed to help GPS when GPS needs it, otherwise it may hurt GPS performance. In a situation, when GPS positioning is already good, blending with poor Wi-Fi positioning may result in overall poor hybrid positioning as compared to GPS only positioning. Lastly, Wi-Fi positioning accuracy needs to be assessed before blending with GPS. If Wi-Fi positioning itself is not good then blending it with GPS will not provide good results. Typically, GPS and Wi-Fi fixes are blended in a feed-forward fashion using a weighted sum of their fixes, which is further explained with the help of FIG. 1.
FIG. 1 illustrates a conventional positioning system 100 using feed forward blending.
As illustrated in the figure, conventional positioning system 100 includes an AP database 102, a Wi-Fi Position Engine (PE) 104, a Wi-Fi scan module 106, a hybrid PE 108 and a GNSS PE 110. For illustrative purposes, AP database 102. Wi-Fi PE 104, Wi-Fi scan module 106, hybrid PE 108 and GNSS PE 110 are shown as distinct elements, however, in some cases, at least two of AP database 102, Wi-Fi PE 104, Wi-Fi scan module 106, hybrid PE 108 and GNSS PE 110 may be combined as a unitary element.
AP database 102 contains the location of APs and is managed by a database vendor such as Google or Navizon. Generally, a database vendor collects the location of APs by “wardriving” efforts and/or crowd sourced using mobile phones such as the iPhone and the Android phone. Wardrivers use a Wi-Fi equipped device together with a GPS device to record the location of wireless networks. When a street driver finds a good GPS location, he determines that at that GPS location, there are certain number of APs and reports those APS with their respective signal strength to the database vendor. Database vendors collect this information from multiple users at different times to build up their database. AP database 102 is operable to bi-directionally communicate with Wi-Fi PE 104 via a signal 112.
Wi-Fi scan module 106 is operable to receive the scan parameters from Wi-Fi PE 104 via a signal 114 for scanning the APs and to provide the scan results back to Wi-Fi PE 104 via a signal 116. Wi-Fi scan module 106 performs the scan by sending probe requests to all the APs in the vicinity. Typically, an AP will respond with a probe response, which includes the Basic Service Set Identifier (BSSID) and Receive Signal Strength (RSS) of each AP. BSSID refers to Media Access Control (MAC) address for an AP, which uniquely identifies that AP. The scan results from APs include BSSIDs and RSSs for all the APs, which are forwarded to Wi-Fi PE 104 via signal 116. In one example, Wi-Fi scan module 106 communicates with a Wireless Local Area Network chipset (WLAN) and receives the list of scanned APs. In particular, the WLAN chipset executes the scan, wherein Wi-Fi scan module 106 sends a request and gets a response from the WLAN chipset.
Wi-Fi PE 104 is operable to provide Wi-Fi positioning based on the inputs from AP database 102, and Wi-Fi scan module 106. Wi-Fi PE 104 is operable to receive AP locations from AP database 102 based on the AP list provided as a result of Wi-Fi scan. Wi-Fi PE 104 is further operable to determine the user location based on the AP locations. Wi-Fi PE 104 provides a Wi-Fi only output via a signal 118 and also a Wi-Fi positioning report to hybrid PE 108 via a signal 120.
GNSS PE 110 is operable to receive the satellite measurements (not shown) and compute the location of a GNSS receiver. GNSS PE 110 provides a GNSS report to hybrid PE 108 via a signal 124. GNSS PE 110 triangulates the position based on a pseudo-range that indicates how far the user is from the satellites and the user velocity, GNSS PE 110 may include a Kalman filter, which filters this information across time. Kalman filter algorithm is an optimized method of determine the best estimation of a system's current state. The algorithm works in a two-step process. In the prediction step, the Kalman filter produces estimates of the true unknown values, along with their uncertainties. Once the outcome of the next measurement is observed, these estimates are updated using a weighted average, with more weight being given to estimates with higher certainty. The Kalman filter keeps track of the estimated state of the system and the variance or uncertainty of the estimate. The estimate is updated using a state transition model and measurements. Kalman filter receives measurements from multiple satellites and determines the effective current location based on the past as well as the new measurements from the satellites.
Hybrid PE 108 is operable to perform blending of Wi-Fi fix and GNSS fix for a user location based on the Wi-Fi positioning report received from Wi-Fi PE 104 and the GNSS report received from GNSS PE 110. Typically, for conventional positioning system 100, GPS and Wi-Fi fixes are blended in a feed-forward fashion using a weighted sum of their fixes. Generally, the weights are based on the uncertainties in the measurement. If the GPS solution is good and the Wi-Fi solution is not as good, more weightage is given to the GPS solution. Alternatively, if the Wi-Fi solution is good and the GPS solution is not as good, more weightage is given to the Wi-Fi solution.
This method has few limitations, which are discussed below. When good Wi-Fi fixes are available only for a short time, blended solution will improve only during that time and will not improve for the later fixes. Since Wi-Fi fix is good only for a short time, more weightage is given to the Wi-Fi solution. If Wi-Fi solution is not good thereafter and the GPS solution was not good throughout, then the blended solution will not improve in the latter part. Additionally, if Wi-Fi and GPS uncertainty estimates are already inaccurate, they will result in poor blending performance. It is possible to give unnecessary weightage to one solution thinking that the fix is good but that may be inaccurate. Errors in GPS or Wi-Fi fix, not reflected in the uncertainty metric will cause deviations in the blended fix.
Additionally Wi-Fi and GPS fixes are typically colored by the past and do not represent independent information, therefore, using a weighted sum is decidedly non-optimal in such cases. Wi-Fi fixes, which is computed based on the visible APs may be more clustered. Using this information multiple times in blending will cause clustering of the blended fixes as well.
What is needed is a blending method for Wi-Fi and GPS that overcomes the problems present in the feed-forward blending method and additionally provides an overall good positioning accuracy.